﻿/*

 * Copyright (c) 2013 Diorge Brognara, Renan Peixoto

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.

*/

using System;
using System.Collections.Generic;

namespace Grafos {
    /// <summary>
    /// Especialização de GrafoPonderado, representa uma árvore com arestas ponderadas
    /// </summary>
    public class ÁrvorePonderada : GrafoPonderado {

        /// <summary>
        /// Quando verdadeiro, assegura que todas as arestas adicionadas não criam ciclos
        /// </summary>
        /// <remarks>
        /// Há uma perda de performance quando ativado, devido a verificação de ciclos a cada aresta adicionada
        /// É recomendado deixar como false durante a aplicação de algoritmos que incluem arestas intesivamente
        /// Caso o algoritmo deva ser testado, utilize o método ÉÁrvore após a execução
        /// Valor padrão é false
        /// </remarks>
        /// <example>
        /// <code>
        /// ÁrvorePonderada a = new ÁrvorePonderada();
        /// a.ModoSeguro = true;
        /// a.AdicionarVértice("v1");
        /// a.AdicionarVértice("v2");
        /// a.AdicionarAresta("v1", "v2");
        /// a.AdicionarAresta("v2", "v1"); // causa erro
        /// </code>
        /// </example>
        /// <seealso cref="Grafo.ÉÁrvore"/>
        public bool ModoSeguro { get; set; }

        /// <summary>
        /// Adiciona uma nova aresta à árvore
        /// </summary>
        /// <param name="a">Aresta a ser adicionada, deve ser uma ArestaPonderada</param>
        /// <remarks>Quando ModoSeguro for ativado, faz verificação para evitar criação de ciclos</remarks>
        /// <exception cref="ArgumentException">É tentado adicionar um loop, ou um ciclo quando o Modo Seguro está ativo,
        /// ou a aresta passada não é ArestaPonderada</exception>
        /// <seealso cref="ModoSeguro"/>
        public override void AdicionarAresta(Aresta a) {
            if (!(a is ArestaPonderada))
                throw new ArgumentException("Árvores ponderadas possuem somente arestas ponderadas");
            AdicionarAresta((ArestaPonderada)a);
        }

        /// <summary>
        /// Adiciona uma nova aresta à árvore
        /// </summary>
        /// <param name="a">Aresta a ser adicionada</param>
        /// <remarks>Quando ModoSeguro for ativado, faz verificação para evitar criação de ciclos</remarks>
        /// <exception cref="ArgumentException">É tentado adicionar um loop, ou um ciclo quando o Modo Seguro está ativo</exception>
        /// <seealso cref="ModoSeguro"/>
        public override void AdicionarAresta(ArestaPonderada a) {
            if (a.ÉLoop)
                throw new ArgumentException("Árvore não podem conter loops");

            base.AdicionarAresta(a);

            if (PossuiCiclo()) {
                Arestas.Remove(a);
                throw new ArgumentException("Tentativa de criar um ciclo na árvore");
            }
        }

        /// <summary>
        /// Adiciona uma nova aresta à árvore
        /// </summary>
        /// <param name="v1">Uma das extremidades da aresta</param>
        /// <param name="v2">Uma das extremidades da aresta</param>
        /// <remarks>Quando ModoSeguro for ativado, faz verificação para evitar criação de ciclos</remarks>
        /// <exception cref="ArgumentException">É tentado adicionar um loop, ou um ciclo quando o Modo Seguro está ativo</exception>
        /// <seealso cref="ModoSeguro"/>
        public override void AdicionarAresta(Vértice v1, Vértice v2) {
            AdicionarAresta(new ArestaPonderada(v1, v2));
        }

        /// <summary>
        /// Adiciona uma nova aresta à árvore
        /// </summary>
        /// <param name="v1">Uma das extremidades da aresta</param>
        /// <param name="v2">Uma das extremidades da aresta</param>
        /// <param name="valor">Valor da aresta ponderada</param>
        /// <remarks>Quando ModoSeguro for ativado, faz verificação para evitar criação de ciclos</remarks>
        /// <exception cref="ArgumentException">É tentado adicionar um loop, ou um ciclo quando o Modo Seguro está ativo</exception>
        /// <seealso cref="ModoSeguro"/>
        public override void AdicionarAresta(Vértice v1, Vértice v2, float valor) {
            AdicionarAresta(new ArestaPonderada(v1, v2, valor));
        }

        /// <summary>
        /// Adiciona uma nova aresta à árvore
        /// </summary>
        /// <param name="v1">Nome de uma das extremidades da aresta</param>
        /// <param name="v2">Nome de uma das extremidades da aresta</param>
        /// <remarks>Quando ModoSeguro for ativado, faz verificação para evitar criação de ciclos</remarks>
        /// <exception cref="ArgumentException">É tentado adicionar um loop, ou um ciclo quando o Modo Seguro está ativo</exception>
        /// <seealso cref="ModoSeguro"/>
        public override void AdicionarAresta(string v1, string v2) {
            AdicionarAresta(BuscarVértice(v1), BuscarVértice(v2));
        }


        /// <summary>
        /// Cria uma árvore ponderada a partir de uma lista de vértices
        /// </summary>
        /// <param name="vértices">Lista de vértices com Pi e Lambda já calculados</param>
        /// <param name="modoSeguro">Indica se a árvore deve verificar presença de ciclos</param>
        /// <returns>Uma nova árvore que respeita os predecessores passados</returns>
        /// <remarks>
        /// Acionar o modo seguro pode causar problemas de performance, especialmente com muitos vértices
        /// A propriedade Pi dos vértices é utilizada para mapear os predecessores
        /// A propriedade Lambda dos vértices é utilizada para dar peso às arestas
        /// Se pegarmos o valor absoluta da diferença de lambda entre dois vértices vizinhos, este era o peso original da aresta
        /// Tal propriedade também é verdadeiro para casos de árvores com mais de uma raíz (mais de um Lambda = 0)
        /// Nos casos de múltiplas raízes, assume-se que o Lambda é a distância até a raíz mais próxima
        /// </remarks>
        /// <example>
        /// <code>
        /// Vértice[] v = Vértice.CriarConjuntoVértices("V", 5);
        /// v[0].Pi = null; // V1 é raíz
        /// v[0].Lambda = 0;
        /// v[1].Pi = v[0]; // V1-V2 (2)
        /// v[1].Lambda = 2;
        /// v[2].Pi = v[1]; // V2-V3 (3)
        /// v[2].Lambda = 5;
        /// v[3].Pi = null; // V4 é raíz
        /// v[3].Lambda = 0;
        /// v[4].Pi = v[3]; // V4-V5 (4)
        /// v[4].Lambda = 4;
        /// ÁrvorePonderada a = ÁrvorePonderada.GerarDePredecessores(v, true);
        /// // forma a árvore de vértices "V1", "V2", "V3", "V4", "V5", com as arestas
        /// // V1-V2 (2), V2-V3 (3), V4-V5 (4)
        /// </code>
        /// </example>
        public static ÁrvorePonderada GerarDePredecessores(IEnumerable<Vértice> vértices, bool modoSeguro) {
            ÁrvorePonderada a = new ÁrvorePonderada();
            Vértice novo;
            Vértice raíz;

            a.ModoSeguro = modoSeguro;

            // cria o novo conjunto de vértices, copiando o antigo
            foreach (Vértice v in vértices) {
                novo = new Vértice(v.Nome);
                novo.Pi = v.Pi;
                novo.Lambda = v.Lambda;
                if (novo.Lambda == 0)
                    raíz = novo;
                novo.Tag = v.Tag;
                a.AdicionarVértice(novo);
            }

            // atualiza o Pi de cada vértice para apontar para os novos vértices
            foreach (Vértice v in a.Vértices.Values) {
                if (v.Pi != null)
                    v.Pi = a.Vértices[v.Pi.Nome];
            }

            // cria as arestas a partir do Pi
            foreach (Vértice v in a.Vértices.Values) {
                if (v.Pi != null)
                    a.AdicionarAresta(v, v.Pi, Math.Abs(v.Lambda - v.Pi.Lambda));
            }

            return a;
        }
    }
}
